This invention relates to an N-point discrete Fourier transform calculator. The calculator is for calculating discrete Fourier transforms (hereafter abbreviated to DFT) of a sequence of N-point discrete samples. Inasmuch as calculation of inverse discrete Fourier transforms (hereafter abbreviated to IDFT) of DFT's is similar in nature as will later be described, the calculator is capable of calculating also IDFT's. The number of points N is herein equal to an even number and therefore to 2M, where M represents an integer.
DFT is known as a mathematical operation for finding a frequency spectrum of a sequence of a finite number of discrete signals and is useful in digitally processing the signals. For example, a DFT calculator is used as a digital spectrum analyser and a digital filter. DFT calculators are used also in modulators and demodulators of a transmultiplexer for interconnecting a time division multiplex (TDM) network and a frequency division multiplex (FDM) network.
A sequence of DFT's F.sub.k (k=0, 1, . . . , and N-1) of a sequence of N-point discrete samples f.sub.n (n=0, 1, . . . , and N-1) is defined by: ##EQU1## IDFT is an inverse operation of DFT. Namely, a sequence of IDFT's f.sub.n of the DFT's F.sub.k is calculated according to: ##EQU2## As regards the type of calculation, Equations (1) and (2) are equivalent to each other except for the factor 1/N and the sign of the argument of the exponential function. It is therefore possible to use a DFT calculator both for DFT's and IDFT's as mentioned hereinabove. Due to periodic nature of the discrete values f.sub.n and F.sub.k, it is possible to regard f.sub.N and F.sub.N to be equal to f.sub.0 and F.sub.0, respectively.
Merely for convenience of description, let use be made, instead of Equations (1) and (2), of: ##EQU3## It should be pointed out here that multiplication has had to be carried out N times in order to calculate Equation (3) for a particular value of the ordinal numbers n used to generally represent any member of the DFT's or IDFT's. It is therefore mandatory to perform multiplication N.sup.2 times for all discrete samples f.sub.n. With an increase in the number of points N, the number of times of multiplication grows quadratically so as to render a real-time DFT calculator inhibitingly bulky.
In various publications, fast Fourier transform (hereafter abbreviated to FFT) calculators are described. An FFT calculator is usable when the number of points N is divisible into products of integers. An example of such publications is a book entitled "Theory and Application of Digital Signal Processing" written by L. R. Babiner and B. Gold and published by Prentice-Hall, Inc., of New Jersey, U.S.A., pages 598 to 626. According to FFT, it is possible to materially reduce the number of times of multiplication. Particularly when the number of points N is given by a power to two 2.sup.n (the letter "n" being used for the time being with no connection to the letter "n" used elsewhere in the instant specification to generally represent the ordinal numbers of the discrete samples), the number of times of multiplication is reduced to (N/2) log.sub.2 N and, in practice, to (N/2)(log.sub.2 N-2) because two of log.sub.2 N stages of the multiplication are mere multiplication by l and j, respectively.
Both the input discrete samples F.sub.k of a sequence supplied to a DFT calculator and the output DFT's or IDFT's f.sub.n are given by complex data in general. It is, however, often the case that the input data are limited to real data and/or that only real parts are necessary among the complex output data. Even in such a case, it has been infeasible to reduce the number of times of multiplication with a conventional DFT calculator. Inasmuch as a speed of arithmetic operation of a digital system is dependent on the number of times of multiplication, it has been impossible to improve the speed with a conventional DFT calculator. This applies to power consumption of the digital system.